package DoExercise.HSP_ZCY.A015_暴力递归;

public class Code01_汉诺塔1
{
    public static void main(String[] args)
    {
        int n = 3;
        //        hanoi1(n);
        //        System.out.println("============");
        hanoi2(n);
        System.out.println("============");
    }
    
    public static void hanoi1(int n)
    {
        leftToRight(n);
    }
    
    public static void leftToRight(int n)
    {
        if (n == 1)
        {
            System.out.println("Move 1 from left to right");
            return;
        }
        leftToMid(n - 1);
        System.out.println("Move " + n + " from left to right");
        midToRight(n - 1);
    }
    
    public static void leftToMid(int n)
    {
        if (n == 1)
        {
            System.out.println("Move 1 from left to mid");
            return;
        }
        leftToRight(n - 1);
        System.out.println("Move " + n + " from left to mid");
        rightToMid(n - 1);
    }
    
    public static void rightToMid(int n)
    {
        if (n == 1)
        {
            System.out.println("Move 1 from right to mid");
            return;
        }
        rightToLeft(n - 1);
        System.out.println("Move " + n + " from right to mid");
        leftToMid(n - 1);
    }
    
    public static void midToRight(int n)
    {
        if (n == 1)
        {
            System.out.println("Move 1 from mid to right");
            return;
        }
        midToLeft(n - 1);
        System.out.println("Move " + n + " from mid to right");
        leftToRight(n - 1);
    }
    
    public static void midToLeft(int n)
    {
        if (n == 1)
        {
            System.out.println("Move 1 from mid to left");
            return;
        }
        midToRight(n - 1);
        System.out.println("Move " + n + " from mid to left");
        rightToLeft(n - 1);
    }
    
    public static void rightToLeft(int n)
    {
        if (n == 1)
        {
            System.out.println("Move 1 from right to left");
            return;
        }
        rightToMid(n - 1);
        System.out.println("Move " + n + " from right to left");
        midToLeft(n - 1);
    }
    
    public static void hanoi2(int n)
    {
        if (n > 0)
        {
            func(n, "left", "right", "mid");
        }
    }
    
    /**
     * 从左到右
     * 1 将 1 - N-1 移动到 other，腾出N
     * 2 将 N 移动到 right，有效移动N
     * 3 将 1 - N-1 移动到 right，完成移动
     *
     * @param N
     * @param from
     * @param to
     * @param other
     */
    public static void func(int N, String from, String to, String other)
    {
        if (N == 1)
        {
            System.out.println("Move 1 from " + from + " to " + to);
        } else
        {
            func(N - 1, from, other, to);
            System.out.println("Move " + N + " from " + from + " to " + to);
            func(N - 1, other, to, from);
        }
    }
}
